Stream ciphers convert a plaintext to a ciphertext one bit at a time. In general, a stream cipher has a keystream generator that outputs a keystream consisting of a series of bits that, for perfect security, vary in value in an unpredictable manner. Each keystream bit is combined using a Boolean exclusive-OR operation (XOR) with an incoming bit of the plaintext, resulting in an output bit of the ciphertext. Thus, an additive stream cipher encrypts a plaintext by bitwise adding a pseudo-randomly generated keystream into the plaintext, modulo two.
For decryption, the ciphertext bits are XORed with an identical keystream to recover the plaintext bits. Accordingly, a stream cipher is ideally suited to encrypting a continuing stream of data, such as the data passing over a network connection between two computers or other network elements. Also, the security of a stream cipher resides in the randomness of the keystream, however, the keystream must be reproducible in identical form at decryption time. Therefore, design of the keystream generator is essential to security and practical operation.
FIG. 1A is a simplified block diagram of a stream cipher. A key K 401 is fed to keystream generator 402, which outputs keystream 410. Plaintext 412 is encrypted by an encryption function 416 based on keystream 410. As a result, ciphertext output 414 is produced.
The keystream generator of such a stream cipher can be described in terms of a state update function and an output function. For example, in FIG. 1A, keystream generator 402 has internal state information 404, a next state function 406 (state update function), and output function 408. The state update function maps the internal state of the keystream generator at one instant to its next value. The output function maps the internal state to a segment of keystream, and the keystream is defined as the concatenation of the values of the output function. Further background information on stream ciphers is provided in B. Schneier, “Applied Cryptography: Protocols, Algorithms and Source Code in C,” 2nd ed. (New York: John Wiley & Sons, 1996).
Block ciphers such as the Data Encryption Standard (DES) are popularly used for encryption of computer communications. However, empirical evidence indicates that stream ciphers are faster than block ciphers at equivalent security levels. For example, in practical evaluation, the stream ciphers RC4 and SEAL have been determined to be significantly faster than any secure block cipher when implemented on general-purpose computer processors. Further, RC4 and SEAL have survived years of scrutiny by cryptanalysts. SEAL is described in U.S. Pat. No. 5,454,039; U.S. Pat. No. 5,675,652; U.S. Pat. No. 5,835,597; Rogaway, P. and Coppersmith, D., “A Software-Optimized Encryption Algorithm”, Proceedings of the 1994 Fast Software Encryption Workshop, Lecture Notes In Computer Science, Volume 809, Springer-Verlag, 1994, pp. 56–63; Rogaway, P. and Coppersmith, D., “A Software-Optimized Encryption Algorithm”, Journal of Cryptology, Volume 11, Number 4, Springer-Verlag, 1998, Pages 273–287, and in the file named “seal-abstract.html” in the folder “˜rogaway/papers/” of the domain “cs.ucdavis.edu” on the World Wide Web (www). Both SEAL and RC4 are discussed in Schneier.
Further, theoretically, a stream cipher is inherently immune to a chosen plaintext attack, and can contain more state information than a block cipher. A block cipher needs to have both encryption and decryption to be secure, and needs to have the avalanche property from the middle to both ends. For example, changing a single bit in the middle of the cipher should change each bit of the input and the output with probability of about ½. Also, the stream cipher has the advantage that its outputs are ordered, while a block cipher must be able to efficiently compute every possible output in any possible order. As a result, for many applications stream ciphers are now clearly preferable over block ciphers.
Unfortunately, many stream ciphers have a significant limitation; most cannot efficiently seek to an arbitrary location in their keystream. In this context, seeking to an arbitrary location in the keystream means generating a segment of keystream that is conceptually located an arbitrary number of bits ahead of that portion of keystream that would be generated by ordinary operation of the keystream in its then-current state. This capability is required for numerous practical applications. For example, in a communications protocol that uses unreliable transport, there is no guarantee that data packets of a particular flow will arrive in order, or arrive at all. Examples of such protocols include Internet Protocol (IP), UDP, and RTP. Such protocols commonly experience loss and reorder of packets in practice. Therefore, for a flow that includes successive packets a, b, and c, a cipher may need to decrypt packet c before it decrypts packet b if packet c arrives before packet b. A stream cipher can be used to provide privacy for data communicated using such protocols, if the cipher can seek to the proper location in the keystream for packet c based on a sequence number.
Similarly, an encrypted disk partition or file system can use a stream cipher if the cipher supports the seek operation.
These examples do not require the random access capability of a block cipher, in which all inputs are equally simple to compute. Rather, the example applications require the capability to seek into the keystream, with a seek time that is not significant relative to the time required to generate the keystream itself. In this context, “seek” is used in the same sense as used in the POSIX and ANSI C functions for repositioning the offset of a file descriptor.
In one past approach to providing a stream cipher with a seek capability, the state update function is made linear in some field. In this approach, a seek is a composition of linear operations, and therefore is itself linear. This approach is similar to using a block cipher in counter mode, which imposes requirements on the output function that are similar to the requirements on block ciphers.
In an alternative approach, as taken by Rogaway et al. in the design of the SEAL cipher, a special seek function is defined that pseudo-randomly maps an index and a fixed key to an internal state of a keystream generator. Based on this state information, the keystream generator can generate a length of keystream. The keystream for the cipher is defined to be the concatenation of the keystreams generated for each index, with indices in ascending order. Effectively, this approach creates a stream cipher that can seek to some regularly spaced locations in its keystream.
While this approach is satisfactory for many applications, some applications may require the ability to seek to an arbitrary location in the keystream. For example, an encrypted database containing many small records could have this requirement. In addition, the seek function approach adds security requirements. The seek function itself must be secure, and the seek and advance functions must be such that they do not interact in an insecure way.
Based on the foregoing, there is a clear need for an additive stream cipher method that can seek to an arbitrary location in its keystream.
There is a specific need for a stream cipher that provides a keystream seek capability without using a linear state update function, and without a special seek function.
There is also a need to provide such a stream cipher in an embodiment that achieves excellent performance when executed in software implemented for general-purpose computer processors.
Some cryptographic systems benefit from the property of forward secrecy, in which the compromise of a current key does not cause or imply the compromise of all messages that were previously encrypted with that key or another key. For example, the Internet Key Exchange (IKE) can, optionally, provide forward secrecy by establishing session keys using the Diffie-Hellman key exchange with ephemeral public keys, as described in D. Harkins et al., “The Internet Key Exchange (IKE),” RFC 2409, November 1998, and H. Orman, “The OAKLEY Key Determination Protocol,” RFC 2412, November 1998.
In general, a cryptographic system that encrypts a sequence of messages m0, m1, m2 . . . provides forward security (or “forward secrecy”) against an adversary A if the disclosure of all the secret state values of the system between the encryption of messages mi and mi+1 does not compromise to A any of the messages m0, m1, mi . . . , which were encrypted before such disclosure, provided that A was not capable of compromising such messages before such disclosure.
Forward security can be provided in a symmetric key encryption system through a process of key updating. Key updating is a technique for providing forward secrecy by using a pseudorandom function to update a key, thus producing a sequence of keys. A key updating function maps a key to another key. For example, a key updating function f may produce a sequence K0,K1=f(K0),K2=f(K1), . . . , kl of l keys. In a practical key updating function, it is computationally infeasible to compute Kj given Ki whenever j<i.
A segmented stream cipher such as SEAL, the cipher described above, and Counter Mode, is used in cryptographic systems in which the plaintext and ciphertext are segmented. Each segment is identified by a non-repeating integer. Symbolically, the keystream may be viewed as composed of 2t segments S0, S1, . . . , and the segments are indexed by a t-bit value. A segmented cipher that provides forward secrecy could associate a distinct key in a key updating sequence with each segment of the keystream. Thus,Si=g(Ki),wherein the function g maps keys to segments. Based on the foregoing, there is a clear need in this field for a way to provide forward security in a segmented stream cipher.
A cipher that provides forward security may have vulnerability to run-up attacks. A run-up attack is a denial-of-service attack against a protocol that uses the cipher. An adversary sends bogus ciphertexts with packet indices that are far in advance of the last valid index. The receiver of such packets cannot distinguish such packets as invalid without “running up” the cipher to the proper keystream location. Therefore, there is a need for a way protect against run-up attacks.
Embodiments described herein include a key updating process for providing forward security in a packet security protocol such as IPSec. Packet data communication is often carried using an unreliable data network transport protocol. Examples of unreliable transport protocols include IP, UDP, and RTP. Such protocols may deliver packets out of sequence, and may fail to deliver some packets at all. As a result, a cipher that provides forward secrecy, and is used by a node that receives packets, may need to generate segment keys out of order, for corresponding out-of-order packets. Further, the cipher cannot discard segment keys that have not been used and that may be needed.
In such an approach, a positive constraint is that actual security protocols for use over unreliable transport permit only a certain amount of packet reordering, and reject packets with indices that precede the most recently received index by too great a factor. For example, the IPSec encapsulating security payload (ESP) includes a sequence number in each packet, enabling a receiver to determine the proper sequencing of the packets, and to determine if a packet has been received before. Packets with a sequence number (“index”) that precedes the most recently received index by too great a factor are dropped. The receiver maintains a replay window, which may be a list of which index values in a fixed range have been received, and the window moves forward as legitimate packets are received. Thus, such protocols enforce a sliding window within which keys may be generated. Keys are not generated for just-received packets that are too old. A pseudocode description of this approach is:
if the index I precedes the replay window thenreject the packetelseif i is already in the replay window thenreject the packetelseauthenticate and decrypt the packet;add i to the replay window;slide replay window forward if neededend ifend ifAccordingly, there is a need for a cipher providing forward security that can efficiently implement this approach, to provide resistance to run-up attacks.
Forward secrecy is desirable for use with group keys that protect communications among multiple nodes or devices, such as in Internet multicasting. When multiple devices have a key, the chance of compromising the key increases. Forward secrecy can solve this problem, by ensuring that compromise of a current key does not affect previous traffic.
Forward secrecy is also desirable to enhance the security of system logs, as described in M. Bellare et al., “Forward Integrity for Secure Audit Logs,” Technical Report, 1997, and in a paper presented by B. Schneier et al., USENIX Security Symposium, 1997. By authenticating each log message with a forward authentication code, a logging system gains the feature that any modification or removal of log messages will be evident to an auditor who knows the authentication key. By updating the authentication key using a one-way function after each message is authenticated, the log system also gains forward secrecy, and an intruder who gains control of a system protected by such a log is unable to unalterably erase the log messages that betray his presence.
In the past, message authentication codes with forward security have been described, especially in the context of secure logging systems. Digital signature systems with forward security are also known. However, these descriptions do not relate to a security system that provides privacy, do not provide for key updating within a cryptographic protocol, and do not address key generation in the presence of imperfect synchronization.
Keystream generators with a random-access property are known. However, these generators do not provide forward security.
Based on the foregoing, there is a clear need in this field for a way to generate keystream or keystream segments for use in encipherment, with forward security.
There is also a need for an approach that provides random access, such that any segment of keystream can be generated on demand.